package com.sheng.leetcode.year2023.month10.day18;

import org.junit.Test;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author by ls
 * @date 2023/10/18
 * <p>
 * 2530. 执行 K 次操作后的最大分数<p>
 * <p>
 * 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。<p>
 * 在一步 操作 中：<p>
 * 选出一个满足 0 <= i < nums.length 的下标 i ，<p>
 * 将你的 分数 增加 nums[i] ，并且<p>
 * 将 nums[i] 替换为 ceil(nums[i] / 3) 。<p>
 * 返回在 恰好 执行 k 次操作后，你可能获得的最大分数。<p>
 * 向上取整函数 ceil(val) 的结果是大于或等于 val 的最小整数。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [10,10,10,10,10], k = 5<p>
 * 输出：50<p>
 * 解释：对数组中每个元素执行一次操作。最后分数是 10 + 10 + 10 + 10 + 10 = 50 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [1,10,3,3,3], k = 3<p>
 * 输出：17<p>
 * 解释：可以执行下述操作：<p>
 * 第 1 步操作：选中 i = 1 ，nums 变为 [1,4,3,3,3] 。分数增加 10 。<p>
 * 第 2 步操作：选中 i = 1 ，nums 变为 [1,2,3,3,3] 。分数增加 4 。<p>
 * 第 3 步操作：选中 i = 2 ，nums 变为 [1,1,1,3,3] 。分数增加 3 。<p>
 * 最后分数是 10 + 4 + 3 = 17 。<p>
 * <p>
 * 提示：<p>
 * 1 <= nums.length, k <= 10^5<p>
 * 1 <= nums[i] <= 10^9<p>
 */
public class LeetCode2530 {

    @Test
    public void test01() {
//        int[] nums = {10, 10, 10, 10, 10};
//        int k = 5;
        int[] nums = {1, 10, 3, 3, 3};
        int k = 3;
        System.out.println(new Solution().maxKelements(nums, k));
    }
}

class Solution {
    public long maxKelements(int[] nums, int k) {
        // 执行 k 次操作，每次从数组 nums 中取出一个元素，加入到分数中，并将这个元素除 3 取整后放入原数组，求最后获取的分数最大值
        // 要求满足元素可重复，自动排序
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
        for (int num : nums) {
            queue.add(num);
        }
        long ans = 0L;
        for (int i = 0; i < k; i++) {
            int index = queue.poll();
            ans += index;
            queue.add((int) Math.ceil(index / 3.0));
        }
        return ans;
    }
}
